743. Network Delay Time
#Algorithm #Algorithm_Dijkstra #Algorithm_Graph #DataStructure-Priority_Queue #DataStructure-Heap
1. 문제
1-1. 원문
You are given a network of n
nodes, labeled from 1
to n
. You are also given times
, a list of travel times as directed edges times[i] = (ui, vi, wi)
, where ui
is the source node, vi
is the target node, and wi
is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k
. Return the minimum time it takes for all the n
nodes to receive the signal. If it is impossible for all the n
nodes to receive the signal, return -1
.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Constraints:
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
- All the pairs
(ui, vi)
are unique. (i.e., no multiple edges.)
1-2. 내용 번역
[시작 노드, 도착 노드, 걸리는 시간]
배열을 하나의 아이템으로 가지는 배열 time이 존재한다. 노드 k에서 시작해서 모든 노드들에 도착하기 까지 걸리는 최소 시간을 구하여라. 만약 하나의 노드라도 도착할 수 없으면(끊어져 있으면) -1을 리턴해라.
2. 문제 이해
2-1. 내용 이해
'노드 k에서 시작해서 모든 노드들에 도착하기 까지 걸리는 최소 시간'이란 노드와 노드 사이를 병렬적으로 이동한다고 생각해야 이해가 된다. 이것을 바꿔서 말하면 '각 도착 노드에 도착했을 때 산출된 결과값들 중에 최대 값을 구해라'라고 이해할 수도 있겠다.
2-2. 접근법 생각
최소 경로? 출발 노드가 있고 모든 노드가 도착노드가 된다? 다익스트라로 풀어야 겠네.
2-3. 적용한 풀이
Dijkstra
3. 구현
class Solution {
val MAX_VALUE = 700000
fun networkDelayTime(times: Array<IntArray>, n: Int, k: Int): Int {
val graphMap: MutableMap<Int, MutableSet<Node>> = mutableMapOf()
val visitedNode: MutableSet<Int> = mutableSetOf()
val timeTakenArr: IntArray = IntArray(n+1){MAX_VALUE}
val pq: PriorityQueue<Node> = PriorityQueue { o1, o2 -> if (o1.time > o2.time) 1 else -1} // 오름차순 정렬
for(time in times) {
// 유향 그래프
(graphMap.getOrPut(time[0]){mutableSetOf()}).add(Node(time[1], time[2]))
}
pq.offer(Node(k, 0))
timeTakenArr[0] = 0 // 노드의 라벨이 1부터 시작하기 때문에 인덱스0은 사용하지 않으므로 무시될 수 있는 값 대입
timeTakenArr[k] = 0
while(pq.isNotEmpty()) {
val curNode = pq.poll()
val curTime = curNode.time
if (visitedNode.contains(curNode.edge).not()) {
visitedNode.add(curNode.edge)
graphMap.getOrDefault(curNode.edge, mutableSetOf()).forEach { (edge, time) ->
if (visitedNode.contains(edge).not()) {
timeTakenArr[edge] = Math.min(timeTakenArr[edge], curTime+time)
pq.offer(Node(edge, timeTakenArr[edge]))
}
}
}
}
val maxTime: Int? = timeTakenArr.maxOrNull()
return if (maxTime == null || maxTime == MAX_VALUE) -1 else maxTime
}
}
data class Node(val edge: Int, val time: Int)